1   /*
2    * Copyright (C) 2009 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import com.google.common.annotations.Beta;
20  import com.google.common.annotations.GwtCompatible;
21  
22  import java.io.Serializable;
23  import java.math.BigInteger;
24  import java.util.NoSuchElementException;
25  
26  /**
27   * A descriptor for a <i>discrete</i> {@code Comparable} domain such as all
28   * {@link Integer} instances. A discrete domain is one that supports the three basic
29   * operations: {@link #next}, {@link #previous} and {@link #distance}, according
30   * to their specifications. The methods {@link #minValue} and {@link #maxValue}
31   * should also be overridden for bounded types.
32   *
33   * <p>A discrete domain always represents the <i>entire</i> set of values of its
34   * type; it cannot represent partial domains such as "prime integers" or
35   * "strings of length 5."
36   *
37   * <p>See the Guava User Guide section on <a href=
38   * "http://code.google.com/p/guava-libraries/wiki/RangesExplained#Discrete_Domains">
39   * {@code DiscreteDomain}</a>.
40   *
41   * @author Kevin Bourrillion
42   * @since 10.0
43   */
44  @GwtCompatible
45  @Beta
46  public abstract class DiscreteDomain<C extends Comparable> {
47  
48    /**
49     * Returns the discrete domain for values of type {@code Integer}.
50     * 
51     * @since 14.0 (since 10.0 as {@code DiscreteDomains.integers()})
52     */
53    public static DiscreteDomain<Integer> integers() {
54      return IntegerDomain.INSTANCE;
55    }
56  
57    private static final class IntegerDomain extends DiscreteDomain<Integer>
58        implements Serializable {
59      private static final IntegerDomain INSTANCE = new IntegerDomain();
60  
61      @Override public Integer next(Integer value) {
62        int i = value;
63        return (i == Integer.MAX_VALUE) ? null : i + 1;
64      }
65  
66      @Override public Integer previous(Integer value) {
67        int i = value;
68        return (i == Integer.MIN_VALUE) ? null : i - 1;
69      }
70  
71      @Override public long distance(Integer start, Integer end) {
72        return (long) end - start;
73      }
74  
75      @Override public Integer minValue() {
76        return Integer.MIN_VALUE;
77      }
78  
79      @Override public Integer maxValue() {
80        return Integer.MAX_VALUE;
81      }
82  
83      private Object readResolve() {
84        return INSTANCE;
85      }
86  
87      @Override
88      public String toString() {
89        return "DiscreteDomain.integers()";
90      }
91  
92      private static final long serialVersionUID = 0;
93    }
94  
95    /**
96     * Returns the discrete domain for values of type {@code Long}.
97     * 
98     * @since 14.0 (since 10.0 as {@code DiscreteDomains.longs()})
99     */
100   public static DiscreteDomain<Long> longs() {
101     return LongDomain.INSTANCE;
102   }
103 
104   private static final class LongDomain extends DiscreteDomain<Long>
105       implements Serializable {
106     private static final LongDomain INSTANCE = new LongDomain();
107 
108     @Override public Long next(Long value) {
109       long l = value;
110       return (l == Long.MAX_VALUE) ? null : l + 1;
111     }
112 
113     @Override public Long previous(Long value) {
114       long l = value;
115       return (l == Long.MIN_VALUE) ? null : l - 1;
116     }
117 
118     @Override public long distance(Long start, Long end) {
119       long result = end - start;
120       if (end > start && result < 0) { // overflow
121         return Long.MAX_VALUE;
122       }
123       if (end < start && result > 0) { // underflow
124         return Long.MIN_VALUE;
125       }
126       return result;
127     }
128 
129     @Override public Long minValue() {
130       return Long.MIN_VALUE;
131     }
132 
133     @Override public Long maxValue() {
134       return Long.MAX_VALUE;
135     }
136 
137     private Object readResolve() {
138       return INSTANCE;
139     }
140 
141     @Override
142     public String toString() {
143       return "DiscreteDomain.longs()";
144     }
145 
146     private static final long serialVersionUID = 0;
147   }
148   
149   /**
150    * Returns the discrete domain for values of type {@code BigInteger}.
151    *
152    * @since 15.0
153    */
154   public static DiscreteDomain<BigInteger> bigIntegers() {
155     return BigIntegerDomain.INSTANCE;
156   }
157 
158   private static final class BigIntegerDomain extends DiscreteDomain<BigInteger>
159       implements Serializable {
160     private static final BigIntegerDomain INSTANCE = new BigIntegerDomain();
161 
162     private static final BigInteger MIN_LONG =
163         BigInteger.valueOf(Long.MIN_VALUE);
164     private static final BigInteger MAX_LONG =
165         BigInteger.valueOf(Long.MAX_VALUE);
166 
167     @Override public BigInteger next(BigInteger value) {
168       return value.add(BigInteger.ONE);
169     }
170 
171     @Override public BigInteger previous(BigInteger value) {
172       return value.subtract(BigInteger.ONE);
173     }
174 
175     @Override public long distance(BigInteger start, BigInteger end) {
176       return end.subtract(start).max(MIN_LONG).min(MAX_LONG).longValue();
177     }
178 
179     private Object readResolve() {
180       return INSTANCE;
181     }
182 
183     @Override
184     public String toString() {
185       return "DiscreteDomain.bigIntegers()";
186     }
187 
188     private static final long serialVersionUID = 0;
189   }
190   
191   /** Constructor for use by subclasses. */
192   protected DiscreteDomain() {}
193 
194   /**
195    * Returns the unique least value of type {@code C} that is greater than
196    * {@code value}, or {@code null} if none exists. Inverse operation to {@link
197    * #previous}.
198    *
199    * @param value any value of type {@code C}
200    * @return the least value greater than {@code value}, or {@code null} if
201    *     {@code value} is {@code maxValue()}
202    */
203   public abstract C next(C value);
204 
205   /**
206    * Returns the unique greatest value of type {@code C} that is less than
207    * {@code value}, or {@code null} if none exists. Inverse operation to {@link
208    * #next}.
209    *
210    * @param value any value of type {@code C}
211    * @return the greatest value less than {@code value}, or {@code null} if
212    *     {@code value} is {@code minValue()}
213    */
214   public abstract C previous(C value);
215 
216   /**
217    * Returns a signed value indicating how many nested invocations of {@link
218    * #next} (if positive) or {@link #previous} (if negative) are needed to reach
219    * {@code end} starting from {@code start}. For example, if {@code end =
220    * next(next(next(start)))}, then {@code distance(start, end) == 3} and {@code
221    * distance(end, start) == -3}. As well, {@code distance(a, a)} is always
222    * zero.
223    *
224    * <p>Note that this function is necessarily well-defined for any discrete
225    * type.
226    *
227    * @return the distance as described above, or {@link Long#MIN_VALUE} or
228    *     {@link Long#MAX_VALUE} if the distance is too small or too large,
229    *     respectively.
230    */
231   public abstract long distance(C start, C end);
232 
233   /**
234    * Returns the minimum value of type {@code C}, if it has one. The minimum
235    * value is the unique value for which {@link Comparable#compareTo(Object)}
236    * never returns a positive value for any input of type {@code C}.
237    *
238    * <p>The default implementation throws {@code NoSuchElementException}.
239    *
240    * @return the minimum value of type {@code C}; never null
241    * @throws NoSuchElementException if the type has no (practical) minimum
242    *     value; for example, {@link java.math.BigInteger}
243    */
244   public C minValue() {
245     throw new NoSuchElementException();
246   }
247 
248   /**
249    * Returns the maximum value of type {@code C}, if it has one. The maximum
250    * value is the unique value for which {@link Comparable#compareTo(Object)}
251    * never returns a negative value for any input of type {@code C}.
252    *
253    * <p>The default implementation throws {@code NoSuchElementException}.
254    *
255    * @return the maximum value of type {@code C}; never null
256    * @throws NoSuchElementException if the type has no (practical) maximum
257    *     value; for example, {@link java.math.BigInteger}
258    */
259   public C maxValue() {
260     throw new NoSuchElementException();
261   }
262   
263 }